package recursivecode;

/**
 * 功能描述:试验 硬币的组合方案问题, 给定金额1000, 数组中的硬币有 [1, 2, 5, 10, 20, 50, 100, 200] 假定数组中的硬币都是正整数
 * 每种硬币可以取出无穷个,也可以只取一个
 * 可以拼凑指定金额的方案有多少种,
 * 2024/08/15
 *
 * @author ZhangYi
 */
public class CoinCombinationMethod {

	public static void main(String[] args) {
		int[] arr = {5, 10, 50, 100};
		int aim = 1000;
		System.out.println(getCoinCombinationMethod(arr, aim));
		System.out.println(getCoinCombinationMethodFromDp(arr, aim));
		System.out.println(getCoinCombinationMethodFromDpUpgrade(arr,aim));
		System.out.println(getCoinCombinationMethodLaset(arr,aim));
	}




	/**
	 * 获取硬币组合方法 数
	 *
	 * @param arr arr
	 * @param aim 瞄准
	 * @return int
	 * @author ZhangYi
	 */
	private static int getCoinCombinationMethod(final int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim <= 0) {
			return 0;
		}
		return process(arr, aim, 0);
	}

	/**
	 * 流程
	 *
	 * @param arr   arr 金额数组
	 * @param rest  剩余 要找的金额
	 * @param index 索引 从0开始,尝试
	 * @return int
	 * @author ZhangYi
	 */
	private static int process(int[] arr, int rest, int index) {
		// 当rest 为1 时,  arr[index] 为100  此时的 rest 是有可能为-99 ; 小于0的情况发生的,
//		if (rest < 0) {
//			return 0;
//		}
		if (index == arr.length) {
			return rest == 0 ? 1 : 0;
		}
		int dpWays = 0;
		// 当rest 为1 时,  arr[index] 为100  此时的 rest 是有可能为-99 ; 小于0的情况发生的
		//zhang * arr[index] <=rest 已经 限定了 不会超过rest 所以, 函数开头的 rest < 0 的判断是可以取消的
		// 当然保留也是可以的,只不过没有什么必要
		for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
			dpWays += process(arr, rest - zhang * arr[index], index + 1);
		}
		return dpWays;
	}

	/**
	 * 从dp获取硬币组合方法
	 *
	 * @param arr arr
	 * @param aim 瞄准
	 * @return int
	 * @author ZhangYi
	 */
	private static int getCoinCombinationMethodFromDp(final int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim <= 0) {
			return 0;
		}
		int N = arr.length;
		int[][] dp = new int[N + 1][aim + 1];

		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				dp[i][j] = -1;
			}
		}

		dp[N][0] = 1;
		process(arr,aim,0,dp);

		return dp[0][aim];
	}

	private static int process(int[] arr, int rest, int index, int[][] dp) {
//		if (rest < 0) {
//			return 0;
//		}
		if (dp[index][rest] != -1) {
			return dp[index][rest];
		}
		if (index == arr.length) {
			dp[index][rest] = rest == 0 ? 1 : 0;
			return dp[index][rest];
		}


		int dpWays = 0;
		// 当rest 为1 时,  arr[index] 为100  此时的 rest 是有可能为-99 ; 小于0的情况发生的
		//zhang * arr[index] <=rest 已经 限定了 不会超过rest 所以, 函数开头的 rest < 0 的判断是可以取消的
		// 当然保留也是可以的,只不过没有什么必要
		for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
			dpWays += process(arr, rest - zhang * arr[index], index + 1,dp);
		}
		dp[index][rest] = dpWays;
		return dp[index][rest] ;
	}

	/**
	 * 从dp升级获取硬币组合方法 数量
	 *
	 * @param arr arr
	 * @param aim 要拼凑的目标金额
	 * @return int
	 * @author ZhangYi
	 */
	private static int getCoinCombinationMethodFromDpUpgrade(int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim <= 0) {
			return 0;
		}
		int N = arr.length;
		int[][] dp = new int[N + 1][aim + 1];

		dp[N][0] = 1;

		for (int index = N - 1; index >= 0; index--) {
			for (int rest = 0; rest <= aim; rest++) {
				int dpWays = 0;
				// 当rest 为1 时,  arr[index] 为100  此时的 rest 是有可能为-99 ; 小于0的情况发生的
				//zhang * arr[index] <=rest 已经 限定了 不会超过rest 所以, 函数开头的 rest < 0 的判断是可以取消的
				// 当然保留也是可以的,只不过没有什么必要
				for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
					dpWays += dp[index + 1][rest - zhang * arr[index]];
				}
				dp[index][rest] = dpWays;
			}
		}

		return dp[0][aim];
	}


	/**
	 * 获得硬币组合方法laset 版本
	 *
	 * @param arr arr
	 * @param aim 瞄准
	 * @return int
	 * @author ZhangYi
	 */
	private static int getCoinCombinationMethodLaset(final int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim <= 0) {
			return 0;
		}
		int N = arr.length;

		int[][] dp = new int[N + 1][aim + 1];
		dp[N][0] = 1;
		for (int index = N - 1; index >= 0; index--) {
			for (int rest = 0; rest <= aim; rest++) {
				// 当前行,总是看她的上一行
				dp[index][rest] = dp[index + 1][rest];
				// 当rest 为 0 ,1, 2 时, arr[index] 此时为10;
				if (rest - arr[index] >= 0) {
					dp[index][rest] += dp[index][rest - arr[index]];
				}
			}
		}

		return dp[0][aim];
	}
}